#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/11/2 14:42
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-Longest Increasing Subsequence.py
# @Software: PyCharm


class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ll = len(nums)
        if ll <= 0:
            return 0
        a = []
        b = []
        ans = 1
        for i in range(ll):
            u = 1
            e = nums[i]
            lb = len(b)
            if lb > 0:
                l, r = 0, lb - 1
                while l < r:
                    h = (l + r + 1) // 2
                    x = b[h][0]
                    if x >= e:
                        r = h - 1
                    else:
                        l = h
                if b[l][0] < e:
                    if b[l][1] + 1 > u:
                        u = b[l][1] + 1
                    if l+1 < lb:
                        if b[l+1][0] > e and b[l+1][1] <= u:
                            b[l+1] = (e, u)
                    else:
                        b.append((e, u))
                else:
                    if b[l][1] <= u:
                        b[l] = (e, u)
            else:
                b.append((e, u))

            # for j in range(i):
            #     if nums[j] < nums[i]:
            #         if a[j] + 1 > u:
            #             u = a[j] + 1
            if u > ans:
                ans = u
            # a.append(u)
        return ans


def main():

    solve = Solution()
    samples = [
        ([10, 9, 2, 5, 3, 7, 101, 18], 4),
    ]
    for i in range(len(samples)):
        nums = samples[i][0]
        ans = samples[i][1]
        answer = solve.lengthOfLIS(nums)
        print('sample', i+1, ':')
        print('  nums:', nums)
        print('  out:', answer, '| ans:', ans, '|', 'accept ^_^' if answer == ans else 'wrong @.@')


if __name__ == '__main__':
    main()